Data Structures & Algorithms - Prob Set 1¶
Student: Henry Baker 228755
Teacher: Prof. Drew Dimmery
Due: 22/02/2024
Q1: (2 points) Two's Complement¶
Convert the following decimal integers into 8-bit Two’s Complement signed integers. If that isn’t possible, explain why it isn’t.
[x] a) 24
[x] b) 156
[x] c) -37
[x] d) 16
a) 24 = 00011000
- convert to binary:
- 24 / 2 = 12 remainder 0
- 12 / 2 = 6 remainder 0
- 6 / 2 = 3 remainder 0
- 3 / 2 = 1 remainder 1
- 1 / 2 = 0 remainder 1
- top2bottom: 11000
- pad out with 0s
- sign bit: 0
b) 156 = out of range
- (max pos value is 127)
c) -37 = 11011011
- convert to binary:
- 37 / 2 = 18 remainder 1
- 18 / 2 = 9 remainder 0
- 9 / 2 = 4 remainder 1
- 4 / 2 = 2 remainder 0
- 2 / 2 = 1 remainder 0
- 1 / 2 = 0 remainder 1
- top2bottom: 100101
- pad out with 0s: 00100101
- invert: 11011010
- add 1: 11011011
- (sign bit: 1)
d) 16 = 00010000
- convert to binary:
- 16 / 2 = 8 remainder 0
- 8 / 2 = 4 remainder 0
- 4 / 2 = 2 remainder 0
- 2 / 2 = 1 remainder 0
- 1 / 2 = 0 remainder 1
- top2bottom: 10000
- pad out with 0s
- sign bit: 0
Q2: (2 points) Addition & Subtraction¶
Now do the following addition / subtraction problems, highlighting where overflow / underflow errors have occurred. The integers are provided in Two’s Complement notation.
[x] a) 00010010 + 10011100
[x] b) 00011000 + 00001000
[x] c) 01100010 + 00101100
[x] d) 11001111 + 10101001
- a) 10101110 = -82
- b) 00100000 = 32
- c) 10001110 (Overflow)10001110
- This binary represents the decimal number −114 (whereas correct answer is 142 (98 + 44)). Here an overflow error has occurred (NB 127 is the max positive value that can be represented by 8 bit signed integer two's complement).
- d) 01111000(101111000) (Overflow)
- where the 1 at the most signficant end is dropped in an 8 bit representation. Here again we have an overflow problem as the sum of two negative numbers (−49 + -87) gives us a result that appears as a positive number in two's complement. The overflow occurs because the true sum extends beyond the representable range of negative values in an 8-bit signed integer (-128), thus wrapping around to the positive side of the range
Q3:(2 points) Fractions -> Floating Points¶
Convert the following fractions into 8-bit floating point (1 sign bit, 3 exponent bits and 4 mantissa bits). If that isn’t possible exactly, explain why, and show how inaccurate the encoding would be: /
[X] a) 3 1/4
[X] b) -6 1/2
[X] c) 4 1/2
[X] d) 9/256
NB: here I used ChatGPT to understand how to convert fractions into binary - I didn't understand how to convert numbers on the RHS of the decimal point. \
a) 0 100 1010
- Expressing in Binary
- 3 = 11 in binary notation
- To represent 1/4 in binary, multiply by 2 repeatedly, taking the integer part of each result:
- 1/4 = 0.25; 0.25x2 = 0.5 - since < 1, binary digit corresponding to the power of -1 (2^-1) is 0 - we go again; 0.5x2 = 1, since >= 1, the binary digit corresponding to the power of -2 (2^-2) is 1; so 1/4 in binary = 0.01
- Together: 3 1/4 = 11.01
- Normalising
- x2^1
- Combining
- Sign bit = 0
- Exponent bits = 100
- Mantissa bits = 1010 (NB here we trip the integer 1 which is implicit; to be left with .101 -> 1010
b) 1 101 1010
- Expressing in Binary
- 6 = 110
- 1/2 = 0.5; 0.5x2 = 1; .1
- Together: 110.1
- Normalising
- x2^2 Combining
- Sign bit = 1
- Exponent bits = 101
- Mantissa bits = 1010
c) 0 101 0010
- Expressing in Binary
- 4 = 100
- 1/2 = 0.5; 0.5x2 = 1; .1
- Together: 100.1
- Normalising
- x2^2 Combining
- Sign bit = 0
- Exponent bits = 101
- Mantissa bits = 1001
d) cannot be represented exactly within the 8-bit floating-point - combo of exponent & mantissa bits not being able to precisely represent such small values - exponent < (2^-3) (we only have 3 bits) - 9/256 = 0.03515625; closest representable is 0.0703125 ((2^-3) * 1.125). Inaccurate by 0.0971875
Q4. (2 points) Floating point -> Fraction¶
Convert the following 8-bit floating point numbers into fractions. If that isn’t possible, explain why: \
[x] 01101011
[x] 11011001
[x] 11001011
[x] 01111111
a) 27/2 (13.5)
- Sign bit
- 0 = positive
- Exponent bits
- 110 = 6 --> 2^3
- Mantissa bits
- 1101: 1.1011 = 1 + 1/2 + 1/8 + 1/16
b) -17/4 (-6.25)
- Sign bit
- 1 = negative
- Exponent bits
- 101 = 5 -> 2^2
- Mantissa bits
- 1001 = 1.1001 --> = 1 + 1/2 + 1/16
c) -27/8 (-3.375)
- Sign bit
- 1 = negative
- Exponent bits
- 100 = 4 --> 2^1 -Mantissa bits
- 1011 = 1.1011 --> = 1 + 1/2 + 1/8 + 1/16
d) 31/1 (31.0)
- Sign bit
- 0 = positive
- Exponent bits
- 111 = 7 --> 2^4
- Mantissa bits
- 1111 = 1.1111 -> = 1 + 1/2 + 1/4 + 1/8 + 1/16
Q5. (3 points) Basic Compute Simulation: Vole¶
Write out exactly what will be done (as I did example solution from the lecture slides) by the computer initialized to have nothing in its registers (including the instruction register), A0 in the program counter, and the following data in its main memory: Address Contents A0 14 A1 AA A2 23 A3 AA A4 A3 A5 03 A6 82 A7 34 A8 C0 A9 00 AA B4
- Program Counter initatilised at A0
- 1a Fetch: 14 AA
- 1b Increment: A2
- 2 Decode: Ox14AA
- 0x1 = Load RXY (register R with bit pattern XY)
- 0x4 = register 0x4
- 0xAA = AA bit pattern
- Execute: 0xAA loaded into register R4
- Program Counter: A2
- 1a Fetch: 23 AA
- 1b Increment: A4
- 2 Decode: Ox23AA
- 0x2 = Load RXY (register R with bit pattern XY)
- 0x3 = register 0x3 destination
- 0xAA = AA
- Execute: 0xAA stored into register R3
- Program Counter: A4
- 1a Fetch: A3 03
- 1b Increment: A6
- 2 Decode: OxA303
- 0xA = Rotate ROX (roate bit pattern in register R one bit to the right X times: low end -> high end)
- 0x3 = register 0x3 destinatiom
- 0x03 = rotate 3 times
- Execute: in R3, 0xAA is rotated 3 times.\
Converting hexadecimal: A = 10; 10 = 1010; AA = 10101010
Rotating 3 times: 01010101
Converting bits: 0101 0101 = 5 5 = 0x55
= 0x55 is stored in R3 \
COME BACK TO CHECK
- Program Counter: A6
- 1a Fetch: 82 34
- 1b Increment: A8
- Decode: 0x8234
- 0x8 = AND RST (the bit patterns in S and R and place the results in T)
- 0x2 = register 0x2 destination
- 0x34 = memory location: registers 0x3 and 0x4
- Execute: in R2, put 0x55AA
THE 0X55 PART IS DEPENDENT ON STEP 3
- Program Counter: A8
- 1a Fetch: C0 00
- 1a Increment: AA
- Decode: 0xC0 00
- Execution: halt
Q6. (2 points) Python Palindrome Function¶
Write a Python function that checks if an input number is a palindrome number (a number that reads the same forward and reverse, e.g. 151) and returns True or False; this function should raise an error if the input is not an integer.
True False Input must be an integer
Q7. (2 points) Using the flask project that you created in the lab, create an About page with the content listed below. You should show in your code that you know how to pass a variable to the render template function. You need to submit the code of your about.html template and the code of your flaskapp.py file, plus a screenshot of the about page in your running app. Include the relevant code in a script listing in a markdown cell of the Jupyter notebook by creating a markdown cell and surrounding it with three backticks (‘‘‘: on a US keyboard, this is above the Tab key, on a German keyboard, this is next to the Backspace key). The screenshot can be inserted using the notebook’s UI (in my Jupyter, an image can be embedded using Edit - Insert Image in a Markdown cell). • a title, e.g. your name • a subtitle, e.g. a description of you • a photo of you • a paragraph about you • links to at least one social media account Hint: You will have to research about how to include images and hyperlinks in flask.
flaskapp.py:
about.html file:
In Q7, I used ChatGPT to support with the CSS styling in the header.
